package com.guaoran.algorithm.node.list;

import com.guaoran.algorithm.common.CommonUtil;
import com.guaoran.algorithm.entity.Node;

import java.util.HashMap;

/**
 * @Desc 深度拷贝带随机指针的链表
 * @Auth gucheng
 * @Date 2020/12/17 下午2:34
 */
public class DeepCopyListWithRandomPointer {
    /**
     * https://leetcode.com/problems/copy-list-with-random-pointer/
     * @param args
     */
    public static void main(String[] args) {
        Node node = CommonUtil.createNodeWithRandom(6);
//        System.out.println(node);
        System.out.println(deepCopyNode2(node));
    }


    /**
     * 深度拷贝 通过 HashMap  存储关系
     * @param head
     * @return
     */
    public static Node deepCopyNode(Node head) {
        if(head == null) return null;

        HashMap<Node,Node> map = new HashMap<>();
        Node node = head;
        while(node!=null){
            if(!map.containsKey(node)) {
                Node temp = new Node(node.data);
                map.put(node, temp);
            }
            Node random = node.random;
            if(random!=null && !map.containsKey(random)){
                Node temp = new Node(random.data);
                map.put(random,temp);
            }
            node = node.next;
        }
        node = head;
        while(node!= null){
            if(head.next!= null) {
                map.get(node).next = map.get(node.next);
            }
            if(node.random !=null){
                map.get(node).random = map.get(node.random);
            }
            node = node.next;
        }

        Node newHead = map.get(head);
        System.out.println(newHead);
        return newHead;
    }


    /**
     * 深度拷贝 没空间复杂度 通过被复制的节点的 next 节点来存储复制的节点
     * @param head
     * @return
     */
    public static Node deepCopyNode2(Node head){
        if(head == null) return  null;

        // 拼接
        Node node = head;
        while (node!=null){
            Node next = node.next;
            Node temp = new Node(node.data);
            node.next = temp;
            temp.next = next;
            node = node.next.next;
        }

        // random
        node = head;
        while(node !=null && node.next !=null){
            Node random = node.random;
            if(random != null ){
                node.next.random = random.next;
            }
            node = node.next.next;
        }
        // 拆分
        Node move = head.next;
        Node newHead = head.next;
        while(head!=null && head.next!=null){
            head.next = head.next.next;
            head = head.next;
            if(move != null && move.next !=null){
                move.next = move.next.next;
                move = move.next;
            }
        }
        return newHead;
    }
}
